
// 力扣30. 串联所有单词的子串
import java.util.*;

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }

        int wordCount = words.length;
        int wordLen = words[0].length();
        int totalLen = wordCount * wordLen;

        if (s.length() < totalLen) {
            return result;
        }

        // 统计 words 中各单词的出现次数
        Map<String, Integer> wordFreq = new HashMap<>();
        for (String word : words) {
            wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
        }

        // 只需检查 0 到 wordLen-1 的起始位置，避免重复检查
        for (int i = 0; i < wordLen; i++) {
            int left = i; // 窗口左边界
            int right = i; // 窗口右边界
            Map<String, Integer> currentFreq = new HashMap<>();

            while (right + wordLen <= s.length()) {
                String currentWord = s.substring(right, right + wordLen);
                right += wordLen;

                if (wordFreq.containsKey(currentWord)) {
                    currentFreq.put(currentWord, currentFreq.getOrDefault(currentWord, 0) + 1);

                    // 如果当前单词出现次数超过 words 中的次数，移动左边界
                    while (currentFreq.get(currentWord) > wordFreq.get(currentWord)) {
                        String leftWord = s.substring(left, left + wordLen);
                        currentFreq.put(leftWord, currentFreq.get(leftWord) - 1);
                        left += wordLen;
                    }

                    // 如果窗口大小等于总长度，记录起始位置
                    if (right - left == totalLen) {
                        result.add(left);
                        // 移动左边界，继续检查后续位置
                        String leftWord = s.substring(left, left + wordLen);
                        currentFreq.put(leftWord, currentFreq.get(leftWord) - 1);
                        left += wordLen;
                    }
                } else {
                    // 遇到不在 words 中的单词，重置窗口
                    currentFreq.clear();
                    left = right;
                }
            }
        }

        return result;
    }
}


// 力扣36. 有效的数独
class Solution1 {
    public boolean isValidSudoku(char[][] board) {
        // 空间换时间
        boolean[][] row = new boolean[10][10]; // 行 (行，数)
        boolean[][] col = new boolean[10][10]; // 列 (列，数)
        boolean[][] nineSquareGrid = new boolean[10][10]; // 九宫格 (格，数)

        int n = board.length;
        int m = board[0].length;
        for(int i =0;i < 9 ;i++){ // 行
            for(int j = 0;j<9;j++){ // 列
                char c = board[i][j];
                if(c=='.') continue;

                int num = c-'0';
                int x = 0;

                // if(i<=2&&j<=2){
                //     x=1;
                // }else if(i<=2&&j>2&&j<=5){
                //     x=2;
                // }else if(i<=2&&j>5){
                //     x=3;
                // }else if(i>2&&i<=5&&j<=2){
                //     x=4;
                // }else if(i>2&&i<=5&&j>2&&j<=5){
                //     x=5;
                // }else if(i>2&&i<=5&&j>5){
                //     x=6;
                // }else if(i>5&&j<=2){
                //     x=7;
                // }else if(i>5&&j>2&&j<=5){
                //     x=8;
                // }else{
                //     x=9;
                // }
                x = (i / 3) * 3 + j / 3;

                if(row[i][num]||col[j][num]||nineSquareGrid[x][num]){
                    return false;
                }
                row[i][num] = true;
                col[j][num] = true;
                nineSquareGrid[x][num] = true;
            }
        }
        return true;

    }
}